#include <iostream>
#include <queue>

using namespace std;

// Binary Tree Node structure
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BinaryTree {
public:
    TreeNode* root;

    BinaryTree() : root(nullptr) {}

    // Function to insert a new node into the binary tree
    TreeNode* insert(TreeNode* node, int val) {
        if (node == nullptr) {
            return new TreeNode(val);
        }

        if (val < node->val) {
            node->left = insert(node->left, val);
        } else {
            node->right = insert(node->right, val);
        }

        return node;
    }

    // Function to find the node with the minimum value in a subtree
    TreeNode* findMin(TreeNode* node) {
        while (node->left != nullptr) {
            node = node->left;
        }
        return node;
    }

    // Function to remove a node from the binary tree
    TreeNode* removeNode(TreeNode* node, int key) {
        if (node == nullptr) {
            return nullptr;
        }

        // Recursively search for the node to remove
        if (key < node->val) {
            node->left = removeNode(node->left, key);
        } else if (key > node->val) {
            node->right = removeNode(node->right, key);
        } else {
            // Node with only one child or no child
            if (node->left == nullptr) {
                TreeNode* temp = node->right;
                delete node;
                return temp;
            } else if (node->right == nullptr) {
                TreeNode* temp = node->left;
                delete node;
                return temp;
            }

            // Node with two children: Get the inorder successor (smallest
            // in the right subtree)
            TreeNode* temp = findMin(node->right);

            // Copy the inorder successor's content to this node
            node->val = temp->val;

            // Delete the inorder successor
            node->right = removeNode(node->right, temp->val);
        }
        return node;
    }

    // Function for level order traversal (BFS) to print the tree
    void levelOrder(TreeNode* node) {
        if (node == nullptr) return;

        queue<TreeNode*> q;
        q.push(node);

        while (!q.empty()) {
            TreeNode* curr = q.front();
            q.pop();
            cout << curr->val << " ";

            if (curr->left != nullptr) q.push(curr->left);
            if (curr->right != nullptr) q.push(curr->right);
        }
    }
};

int main() {
    BinaryTree tree;
    tree.root = tree.insert(tree.root, 50);
    tree.insert(tree.root, 30);
    tree.insert(tree.root, 70);
    tree.insert(tree.root, 20);
    tree.insert(tree.root, 40);
    tree.insert(tree.root, 60);
    tree.insert(tree.root, 80);

    cout << "Original Tree: ";
    tree.levelOrder(tree.root);

    tree.removeNode(tree.root, 20);
    cout << "\nTree after deleting 20: ";
    tree.levelOrder(tree.root);

    tree.removeNode(tree.root, 30);
    cout << "\nTree after deleting 30: ";
    tree.levelOrder(tree.root);

    tree.removeNode(tree.root, 50);
    cout << "\nTree after deleting 50: ";
    tree.levelOrder(tree.root);

    return 0;
}